package com.cn.algorithm02.class08;

import java.util.ArrayList;
import java.util.Arrays;

/***
 * @author: hels
 * @description: 前缀树结构类
 * 实现插入，删除，查询存在个数，前缀和方法
 **/
public class C01_TrieTree {
    public static void main(String[] args) {
        Trie1 trie1 = new Trie1();
        trie1.insert("ab");
        trie1.insert("abc");
        System.out.println(trie1);
        trie1.delete("abc");
        System.out.println(trie1);
//        System.out.println(trie1.prefixNumber("abc"));
//        System.out.println(trie1.prefixNumber("abbc"));
//        System.out.println(trie1.prefixNumber(""));
//        root= Node1{pass=2, end=0, nexts=[
//                Node1{pass=2, end=0, nexts=[
//                        Node1{pass=2, end=0, nexts=[
//                                Node1{pass=2, end=2, nexts=[]}]}]}
//        ]
//        }

//        root=Node1{pass=2, end=0, nexts=[
//                Node1{pass=2, end=0, nexts=[
//                        Node1{pass=2, end=0, nexts=[
//                                Node1{pass=1, end=0, nexts=[
//                                        Node1{pass=1, end=1, nexts=[]}]},
//                                Node1{pass=1, end=1, nexts=[]}]}   ]}]}

    }

    /*
    前缀树节点，带有pass和end表示有多少个存储对象经过
     */
    public static class Node1 {
        public int pass;
        public int end;
        public Node1[] nexts;

        public Node1() {
            pass = 0;
            end = 0;
            nexts = new Node1[26];
        }

        @Override
        public String toString() {
            ArrayList<Node1> newNexts = new ArrayList<>();
            for (Node1 n : nexts) {
                if (n != null) {
                    newNexts.add(n);
                }
            }
            return "Node1{" +
                    "pass=" + pass +
                    ", end=" + end +
                    ", nexts=" + newNexts +
                    '}';
        }
    }

    /*
    前缀树
     */
    public static class Trie1 {
        public Node1 root;

        public Trie1() {
            root = new Node1();
        }

        //数据插入
        public void insert(String word) { // word都为26个英文小写字母
            if (word == null) return;

            Node1 node = root;
            char[] chars = word.toCharArray();
            int path = 0;
            node.pass++;
            for (int i = 0; i < chars.length; i++) {
                path = chars[i] - 'a';
                if (node.nexts[path] == null) {
                    node.nexts[path] = new Node1();
                }
                node = node.nexts[path];
                node.pass++;
            }
            node.end++;
        }

        // 数据删除
        public void delete(String word) {
            if (search(word) == 0) return;

            char[] chars = word.toCharArray();
            Node1 node = root;
            int path = 0;
            node.pass--;
            for (int i = 0; i < chars.length; i++) {
                path = chars[i] - 'a';
                if (--node.nexts[path].pass == 0) { // 加入某个节点--pass=0，意味着该节点
                    node.nexts[path] = null;
                    return;
                }
                node = node.nexts[path];
            }
            node.end--;
        }

        // 数据查询：word存在几个
        public int search(String word) {
            if (word == null || word.length() ==0) return 0;
            char[] chars = word.toCharArray();
            Node1 node = root;
            int path = 0;
            for (int i = 0; i < chars.length; i++) {
                path = chars[i] - 'a';
                if (node.nexts[path] == null) {
                    return 0;
                }
                node = node.nexts[path];
            }
            return node.end;
        }

        // 前缀和查询
        public int prefixNumber(String word) {
            if (word == null || word.length() ==0) return 0;
            char[] chars = word.toCharArray();
            Node1 node = root;
            int path = 0;
            for (int i = 0; i < chars.length; i++) {
                path = chars[i] - 'a';
                if (node.nexts[path] == null) {
                    return 0;
                }
                node = node.nexts[path];
            }
            return node.pass;
        }

        @Override
        public String toString() {
            return "Trie1{" +
                    "root=" + root +
                    '}';
        }
    }


}
